package com.linyaonan.code._03;

import java.util.ArrayList;
import java.util.List;

/**
 * 3. 正则表达式匹配
 * 请实现一个函数用来匹配包括 '.' 和 '*' 的正则表达式。
 * 模式中的字符 '.' 表示任意一个字符，而 '*' 表示它前面的字符可以出现任意次（含 0 次）。
 * 在本题中，匹配是指字符串的所有字符匹配整个模式。
 * 例如，字符串 "aaa" 与模式 "a.a" 和 "ab*ac*a" 匹配，但是与 "aa.a" 和 "ab*a" 均不匹配。
 * 样例：输入：s="aa" p="a*" 输出：true
 *
 * @author: Lin
 * @date: 2020/8/18
 */
public class Main {

    public static void main(String[] args) {
        boolean t1 = match("aaa", "a.a");
        boolean t2 = match("aaa", "ab*ac*a");
        boolean t3 = match("aaa", "aa.a");
        boolean t4 = match("abbbba", "ab*a");
        boolean t5 = match("aaa", "aa*a");

    }

    /**
     * 正则表达式匹配
     * @param s 原始字符
     * @param p 匹配字符
     * @return
     */
    private static boolean match(String s, String p) {
        if (s == null && p == null) {
            return true;
        }
        if (s == null || p == null) {
            return false;
        }
        if (s.equals(p)) {
            return true;
        }

        // 1. start

        // 先处理*匹配0个情况
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < p.toCharArray().length; i++) {
            if (p.charAt(i) == '*') {
                sb.deleteCharAt(sb.length() - 1);
            } else {
                sb.append(p.charAt(i));
            }
        }

        // 替换n*的字符串
        String re = sb.toString();
        if (re.equals(s)) {
            return true;
        }
        // 判断.的占位
        if (re.length() == s.length()) {
            boolean has = true;
            for (int j = 0; j < re.toCharArray().length; j++) {
                if (re.charAt(j) == s.charAt(j) || re.charAt(j) == '.') {
                } else {
                    has = false;
                    break;
                }
            }
            // 针对.占位也可以匹配的情况
            if (has) {
                return true;
            }
        }

        // 1. end

        // 2. 处理*前面的字符 s中不存在的情况
        List<Character> hasNum = new ArrayList<>();
        for (int i = 0; i < p.toCharArray().length; i++) {
            if (p.charAt(i) == '*') {
                hasNum.add(p.charAt(i - 1));
            }
        }

        // 如果s中有一个无法匹配的则返回false
        for (Character c : hasNum) {
            if (!s.contains(String.valueOf(c))) {
                return false;
            }
        }

        // 2. end

        // 3. 将*号前的字符进行填充依次判断



        return false;

    }

}
